利用二分查找找出所给出的数在数组中的下标
输入格式: 第一行输入n和m表示数组有n个数据,m表示要对m个数进行查找
输出格式: 所有输出在一行完成,行末没有多余空格和多余回车。
输入样例:
输出样例:
思路 一道二分查找的模板题
查找不用多说,大部分情况为在数组中寻找某个数,最简单的方法就是遍历一遍,复杂度O(n)
二分查找要求数组有序,核心思想如下:(假设待查找数据为data)
若data大于数组中间位置的值,则data出现在数组后半部分
若data小于数组中间位置的值,则data出现在数组前半部分
依据以上规则,不断比较data和查找范围数组中间的值。二分查找复杂度为O(logn)
如此一想,可以衍生出三分、四分。。。
知识点:二分查找(很重要,这是一种思想,属于面试题常备军)
代码 代码为递归形式,初学便于理解,其实迭代使用的更多。该题解复杂度为O(mlogn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> #include <vector> using namespace std ;int mybinary_find (const vector <int > &ve, int left, int right, int data) { if (left > right) { return -1 ; } int mid = left + (right - left) / 2 ; if (ve[mid] == data) { return mid; } else if (ve[mid] < data) { return mybinary_find(ve, mid + 1 , right, data); } else { return mybinary_find(ve, left, mid - 1 , data); } } int main () { int m, n; scanf ("%d %d" , &n, &m); vector <int > ve; for (int i = 1 ; i <= n; i++) { int id; scanf ("%d" , &id); ve.push_back(id); } for (int i = 1 ; i <= m; i++) { int id; scanf ("%d" , &id); printf ("%d" , mybinary_find(ve, 0 , n - 1 , id)); printf ("%c" , i == m ? '\n' : ' ' ); } return 0 ; }
其实,如果不考虑题目要求,可以标记查找(哈希查找),复杂度O(m),更快
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <iostream> #include <unordered_map> using namespace std ;int main () { int m, n; scanf ("%d %d" , &n, &m); unordered_map <int , int > book; for (int i = 1 ; i <= n; i++) { int id; scanf ("%d" , &id); book[id] = i; } for (int i = 1 ; i <= m; i++) { int id; scanf ("%d" , &id); printf ("%d" , book[id] - 1 ); printf ("%c" , i == m ? '\n' : ' ' ); } return 0 ; }